package com.wangle.server.hot100;

import com.wangle.server.util.ListNode;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

@Service
public class Solution {

    // 长度最小的子数组 前缀双指针
    public int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        int first = 0;
        int second = 0;
        int sum = nums[0];
        while (second<nums.length) {
            if (first>second) {
                second++;
                continue;
            }
            if (sum >= target) {
                len = Math.min(len, second-first+1);
                sum -= nums[first];
                first++;
            } else {
                second++;
                if (second<nums.length) {
                    sum += nums[second];
                    if (sum >= target) {
                        len = Math.min(len, second - first + 1);
                    }
                }
            }

        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    // 长度最小的子数组 暴力法
    public int minSubArrayLen1(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j <nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    len = Math.min(len, j-i+1);
                    break;
                }
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    // 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length - 2; first++) {
            if (nums[first] > 0) {
                break;
            }
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int second = first + 1;
            int third = nums.length - 1;
            while (second < third) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    second++;
                    continue;
                }
                if (nums[first] + nums[second] + nums[third] > 0) {
                    third--;
                } else if (nums[first] + nums[second] + nums[third] < 0) {
                    second++;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                    second++;
                    third--;
                }
            }
        }
        return res;
    }

    //暴力解法 耗时长
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length - 2; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < nums.length - 1; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                int third = second + 1;
                while (third < nums.length && nums[first] + nums[second] + nums[third] < 0) third++;
                if (nums[first] + nums[second] + nums[third] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                }
            }
        }
        return res;
    }

    // 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double median = 0;

        return median;
    }

    // 无重复字符的最长子串
    public int lengthOfLongestSubstring1(String s) {
        List<Character> list = new ArrayList<>();
        int len = 0;
        int len1 = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (list.contains(c)) {
                len = Math.max(len, len1);
                while (list.contains(c)) {
                    list.remove(0);
                }
                list.add(c);
                len1 = list.size();
            } else {
                len1++;
                list.add(c);
            }
        }
        len = Math.max(len, len1);
        return len;
    }

    // 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        String ss = "";
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            List<Character> list = new ArrayList<>();
            int j = 0;
            while (i + j < s.length() && !list.contains(s.charAt(i + j))) {
                list.add(s.charAt(i + j));
                j++;
            }
            len = Math.max(len, j);
        }
        return len;
    }

    // 链表之和
    public ListNode addTwoNums(ListNode node1, ListNode node2) {
        ListNode res = new ListNode(0);
        ListNode cur = res;
        int carry = 0;
        while (node1 != null || node2 != null) {
            int x = node1 == null ? 0 : node1.val;
            int y = node2 == null ? 0 : node2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            if (node1 != null) {
                node1 = node1.next;
            }
            if (node2 != null) {
                node2 = node2.next;
            }
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return res.next;
    }
}
